Searching Points in a KD-Tree

Once points are able to be inserted into the tree, the next step is being able to search for nearby points inside the tree compared to a given target point. Points within a distance of distanceTol are considered to be nearby. The KD-Tree is able to split regions and allows certain regions to be completely ruled out, speeding up the process of finding nearby neighbors.

The naive approach of finding nearby neighbors is to go through every single point in the tree and compare their distances with the target, selecting point indices that fall within the distance tolerance of the target. Instead with the KD-Tree you can compare distance within a boxed square that is 2 x distanceTol for length, centered around the target point. If the current node point is within this box then you can directly calculate the distance and see if the point id should be added to the list of nearby ids. Then you see if your box crosses over the node division region and if it does compare that next node. You do this recursively, with the advantage being that if the box region is not inside some division region you completely skip that branch.

Instructions

• In src/quiz/cluster/kdtree.h fill in the search function.
• Verify that when the code is run, line 115 of cluster.cpp produces the following output:

Test Search
0,1,2,3,

• Experiment by using different point values in the call to search in line 115 of cluster.cpp . Use target points that are close to points in the tree. If the distance tolerance is large enough then those expected nearby point ids should be returned.

Compile/Run

• In src/quiz/cluster , mkdir build
• cd build
• cmake ..
• make
• ./quizCluster

Solution